package cn.com.mdx.sort.heapsort.practice.dynamicmedian;

import cn.com.mdx.sort.SortUtils;

import java.util.Random;

/**
 * <p> 动态中位数
 *
 * @author ：huangy
 * @date ：Created in 2020/10/21 5:47 下午
 */
@SuppressWarnings("unchecked")
public class DynamicMedian<Key extends Comparable<Key>> {

    /**
     * 小数优先队列
     */
    private final int PQ_MIN = 1;

    /**
     * 大数优先队列
     */
    private final int PQ_MAX = 2;

    /**
     * 小数优先的堆，存放大于中位数的数
     */
    private Key[] minPQ;

    /**
     * 小数优先堆存放的数组长度
     */
    private int minPQLength;

    /**
     * 大数优先的堆，存放小于或等于中位数的数
     */
    private Key[] maxPQ;

    /**
     * 小数优先堆存放的数组长度
     */
    private int maxPQLength;

    /**
     * 队列长度
     */
    private int N;

    public DynamicMedian(int capacity) {
        if (capacity <= 0) return;
        int minArrayLength = capacity / 2 + 1;
        int maxArrayLength = capacity / 2 + 1;
        if (capacity % 2 == 1)
            //如果长度为奇数，则大数优先的堆长度要加1
            maxArrayLength = maxArrayLength + 1;

        minPQ = (Key[]) new Comparable[minArrayLength];
        maxPQ = (Key[]) new Comparable[maxArrayLength];
    }

    /**
     * @param key 插入的元素
     * @return void
     * @Author huangy
     * @description //TODO 插入数据
     * @date 2:16 下午 2020/10/22
     **/
    public void insert(Key key) {
        if (minPQ.length + maxPQ.length == N) throw new UnsupportedOperationException("队列已经满了无法再插入数据");
        //如果队列为空，向大数优先堆中插入数据
        if (N == 0) {
            N++;
            maxPQ[++maxPQLength] = key;
            return;
        }
        if (maxPQLength == minPQLength) {
            //1.两个堆的长度相同，则往大数优先堆中插入数据
            //如果插入数据小于小数优先堆中的
            if (SortUtils.great(minPQ[1], key)) maxPQ[++maxPQLength] = key;
            else {
                //说明插入数据在中位数之后，中位数要交换
                maxPQ[++maxPQLength] = minPQ[1];
                minPQ[1] = key;
                //顶部节点下沉
                minSink(minPQ, 1, minPQLength);
            }
            //将插入的节点上浮S
            maxSwim(maxPQ, maxPQLength);
        } else {
            //2.两个堆中小数优先队列的长度较小，则往小数优先队列中插入数据
            if (SortUtils.less(maxPQ[1], key)) minPQ[++minPQLength] = key;
            else {
                minPQ[++minPQLength] = maxPQ[1];
                maxPQ[1] = key;
                //顶部节点下沉
                maxSink(maxPQ, 1, maxPQLength);
            }
            //节点上浮
            minSwim(minPQ, minPQLength);
        }
        N++;
    }

    /**
     * @return Key
     * @Author huangy
     * @description //TODO 获取中位数
     * @date 2:15 下午 2020/10/22
     **/
    public Key median() {
        return maxPQ[1];
    }

    /**
     * @return Key
     * @Author huangy
     * @description //TODO 删除并返回中位数
     * @date 2:15 下午 2020/10/22
     **/
    public Key delMedian() {
        if (isEmpty()) throw new UnsupportedOperationException("队列为空，无法进行删除操作");
        Key median = maxPQ[1];
        if (minPQLength == maxPQLength) {
            maxPQ[1] = minPQ[1];
            SortUtils.exChange(minPQ, 1, minPQLength--);
            minPQ[minPQLength + 1] = null;
            //小数优先队列节点下沉
            minSink(minPQ, 1, minPQLength);
        } else {
            SortUtils.exChange(maxPQ, 1, maxPQLength--);
            maxPQ[maxPQLength + 1] = null;
            //大数优先队列节点下沉
            maxSink(maxPQ, 1, maxPQLength);
        }
        N--;
        return median;
    }

    /**
     * @param pq     优先队列的数据
     * @param index  要上浮节点的位置
     * @param pqType 优先队列类型 1:小数优先队列，2:大数优先队列
     * @return void
     * @Author huangy
     * @description //TODO 节点上浮
     * @date 5:14 下午 2020/10/22
     **/
    private void swim(Key[] pq, int index, int pqType) {
        if (pqType == PQ_MAX)
            while (index > 1 && SortUtils.less(pq[index / 2], pq[index])) {
                SortUtils.exChange(pq, index, index / 2);
                index = index / 2;
            }
        else
            while (index > 1 && SortUtils.great(pq[index / 2], pq[index])) {
                SortUtils.exChange(pq, index, index / 2);
                index = index / 2;
            }
    }

    /**
     * @param pq    优先队列的数据
     * @param index 上浮节点的位置
     * @return void
     * @Author huangy
     * @description //TODO 大数优先队列的上浮
     * @date 5:24 下午 2020/10/22
     **/
    public void maxSwim(Key[] pq, int index) {
        swim(pq, index, PQ_MAX);
    }

    /**
     * @param pq    优先队列的数据
     * @param index 上浮节点的位置
     * @return void
     * @Author huangy
     * @description //TODO 小数优先队列的上浮
     * @date 5:28 下午 2020/10/22
     **/
    public void minSwim(Key[] pq, int index) {
        swim(pq, index, PQ_MIN);
    }

    /**
     * @param pq          优先队列的数据
     * @param index       下沉节点的位置
     * @param arrayLength 数组长度
     * @param pqType      优先队列类型 1:小数优先队列，2:大数优先队列
     * @return void
     * @Author huangy
     * @description //TODO
     * @date 5:35 下午 2020/10/22
     **/
    private void sink(Key[] pq, int index, int arrayLength, int pqType) {
        while (2 * index < arrayLength) {
            int j = 2 * index;
            if (PQ_MAX == pqType) {
                if (j < arrayLength - 1 && SortUtils.less(pq[j], pq[j + 1])) j = j + 1;
                if (SortUtils.less(pq[j], pq[index])) break;
            } else {
                if (j < arrayLength - 1 && SortUtils.great(pq[j], pq[j + 1])) j = j + 1;
                if (SortUtils.great(pq[j], pq[index])) break;
            }
            SortUtils.exChange(pq, index, j);
            index = j;
        }
    }

    /**
     * @param pq          优先队列的数据
     * @param index       下沉节点的位置
     * @param arrayLength 队列长度
     * @return void
     * @Author huangy
     * @description //TODO 大数优先队列节点下沉
     * @date 5:53 下午 2020/10/22
     **/
    public void maxSink(Key[] pq, int index, int arrayLength) {
        sink(pq, index, arrayLength, PQ_MAX);
    }

    /**
     * @param pq          优先队列的数据
     * @param index       下沉节点的位置
     * @param arrayLength 队列长度
     * @return void
     * @Author huangy
     * @description //TODO 小数优先队列节点下沉
     * @date 5:53 下午 2020/10/22
     **/
    public void minSink(Key[] pq, int index, int arrayLength) {
        sink(pq, index, arrayLength, PQ_MIN);
    }

    /**
     * @return boolean
     * @Author huangy
     * @description //TODO 队列是否为空
     * @date 4:08 下午 2020/10/22
     **/
    public boolean isEmpty() {
        return N == 0;
    }

    public static void main(String[] args) {
        int N = 21;
        Random random = new Random();
        DynamicMedian<Integer> dynamicMedian = new DynamicMedian<>(N);
        //插入数据
        for (int i = 1; i <= N; i++)
            dynamicMedian.insert(random.nextInt(N));
        //删除数据
        for (int i = 1; i <= N; i++) {
            SortUtils.printArray(dynamicMedian.maxPQ);
            SortUtils.printArray(dynamicMedian.minPQ);
            System.out.println("中位数是：" + dynamicMedian.delMedian());
        }
    }
}